home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 16 / CU Amiga Magazine's Super CD-ROM 16 (1997-10-16)(EMAP Images)(GB)[!][issue 1997-11].iso / CUCD / Graphics / Ghostscript / source / gxalloc.h < prev    next >
C/C++ Source or Header  |  1996-12-29  |  14KB  |  374 lines
  1. /* Copyright (C) 1995, 1996 Aladdin Enterprises.  All rights reserved.
  2.   
  3.   This file is part of Aladdin Ghostscript.
  4.   
  5.   Aladdin Ghostscript is distributed with NO WARRANTY OF ANY KIND.  No author
  6.   or distributor accepts any responsibility for the consequences of using it,
  7.   or for whether it serves any particular purpose or works at all, unless he
  8.   or she says so in writing.  Refer to the Aladdin Ghostscript Free Public
  9.   License (the "License") for full details.
  10.   
  11.   Every copy of Aladdin Ghostscript must include a copy of the License,
  12.   normally in a plain ASCII text file named PUBLIC.  The License grants you
  13.   the right to copy, modify and redistribute Aladdin Ghostscript, but only
  14.   under certain conditions described in the License.  Among other things, the
  15.   License requires that the copyright notice and this notice be preserved on
  16.   all copies.
  17. */
  18.  
  19. /* gxalloc.h */
  20. /* Memory manager internal definitions for Ghostscript */
  21. /* Requires gsmemory.h, gsstruct.h */
  22.  
  23. #ifndef gs_ref_memory_DEFINED
  24. #  define gs_ref_memory_DEFINED
  25. typedef struct gs_ref_memory_s gs_ref_memory_t;
  26. #endif
  27.  
  28. #include "gsalloc.h"
  29. #include "gxobj.h"
  30.  
  31. /* ================ Chunks ================ */
  32.  
  33. /*
  34.  * We obtain memory from the operating system in `chunks'.  A chunk
  35.  * may hold only a single large object (or string), or it may hold
  36.  * many objects (allocated from the bottom up, always aligned)
  37.  * and strings (allocated from the top down, not aligned).
  38.  */
  39.  
  40. /*
  41.  * Refs are allocated in the bottom-up section, along with struct objects.
  42.  * In order to keep the overhead for refs small, we make consecutive
  43.  * blocks of refs into a single allocator object of type st_refs.
  44.  * To do this, we remember the start of the current ref object (if any),
  45.  * and the end of the last block of allocated refs.  As long as
  46.  * the latter is equal to the top of the allocated area, we can add
  47.  * more refs to the current object; otherwise, we have to start a new one.
  48.  * We assume that sizeof(ref) % obj_align_mod == 0; this means that if we
  49.  * ever have to pad a block of refs, we never add as much as one entire ref.
  50.  */
  51.  
  52. /*
  53.  * When we do a save, we create a new 'inner' chunk out of the remaining
  54.  * space in the currently active chunk.  Inner chunks must not be freed
  55.  * by a restore.
  56.  *
  57.  * The garbage collector implements relocation for refs by scanning
  58.  * forward to a free object.  Because of this, every ref object must end
  59.  * with a dummy ref that can hold the relocation for the last block.
  60.  * In order to put a reasonable upper bound on the scanning time, we
  61.  * limit the length of the objects that contain runs of refs.
  62.  */
  63. #define max_size_st_refs (50 * sizeof(ref))
  64.  
  65. /*
  66.  * Strings carry some additional overhead for use by the GC.
  67.  * At the top of the chunk is a table of relocation values for
  68.  * 16N-character blocks of strings, where N is sizeof(uint).
  69.  * This table is aligned, by adding padding above it if necessary.
  70.  * Just below it is a mark table for the strings.  This table is also aligned,
  71.  * to improve GC performance. The actual string data start below
  72.  * the mark table.  These tables are not needed for a chunk that holds
  73.  * a single large (non-string) object, but they are needed for all other
  74.  * chunks, including chunks created to hold a single large string.
  75.  */
  76.  
  77. /*
  78.  * Define the unit of data manipulation for marking strings.
  79.  */
  80. typedef uint string_mark_unit;
  81. #define log2_sizeof_string_mark_unit arch_log2_sizeof_int
  82. /*
  83.  * Define the quantum of relocation for strings, which determines
  84.  * the quantum for reserving space.  This value must be a power of 2,
  85.  * must be at least sizeof(string_mark_unit) * 8, and (because of the
  86.  * unrolled loops in igcstr.c) currently must be equal to either 32 or 64.
  87.  */
  88. typedef uint string_reloc_offset;
  89. #define log2_string_data_quantum (arch_log2_sizeof_int + 4)
  90. #define string_data_quantum (1 << log2_string_data_quantum)
  91. /*
  92.  * Define the quantum for reserving string space, including data,
  93.  * marks, and relocation.
  94.  */
  95. #define string_space_quantum\
  96.   (string_data_quantum + (string_data_quantum / 8) +\
  97.    sizeof(string_reloc_offset))
  98. /*
  99.  * Compute the amount of space needed for a chunk that holds only
  100.  * a string of a given size.
  101.  */
  102. #define string_chunk_space(nbytes)\
  103.   (((nbytes) + (string_data_quantum - 1)) / string_data_quantum *\
  104.    string_space_quantum)
  105. /*
  106.  * Compute the number of string space quanta in a given amount of storage.
  107.  */
  108. #define string_space_quanta(spacebytes)\
  109.   ((spacebytes) / string_space_quantum)
  110. /*
  111.  * Compute the size of string marks for a given number of quanta.
  112.  */
  113. #define string_quanta_mark_size(nquanta)\
  114.   ((nquanta) * (string_data_quantum / 8))
  115.   
  116. /*
  117.  * To allow the garbage collector to combine chunks, we store in the
  118.  * head of each chunk the address to which its contents will be moved.
  119.  */
  120. /*typedef struct chunk_head_s chunk_head_t;*/    /* in gxobj.h */
  121.  
  122. /* Structure for a chunk. */
  123. typedef struct chunk_s chunk_t;
  124. struct chunk_s {
  125.     chunk_head_t *chead;        /* chunk head, bottom of chunk; */
  126.                     /* csbase is an alias for chead */
  127. #define csbase(cp) ((byte *)(cp)->chead)
  128.     /* Note that allocation takes place both from the bottom up */
  129.     /* (aligned objects) and from the top down (strings). */
  130.     byte *cbase;            /* bottom of chunk data area */
  131.     byte *cbot;            /* bottom of free area */
  132.                     /* (top of aligned objects) */
  133.     obj_header_t *rcur;        /* current refs object, 0 if none */
  134.     byte *rtop;            /* top of rcur */
  135.     byte *ctop;            /* top of free area */
  136.                     /* (bottom of strings) */
  137.     byte *climit;            /* top of strings */
  138.     byte *cend;            /* top of chunk */
  139.     chunk_t *cprev;            /* chain chunks together, */
  140.     chunk_t *cnext;            /*   sorted by address */
  141.     chunk_t *outer;            /* the chunk of which this is */
  142.                     /*   an inner chunk, if any */
  143.     uint inner_count;        /* number of chunks of which this is */
  144.                     /*   the outer chunk, if any */
  145.     bool has_refs;            /* true if any refs in chunk */
  146.         /*
  147.          * Free lists for single bytes in blocks of 1-3 bytes,
  148.          * one per 256 bytes in [csbase..climit).  The chain
  149.          * pointer is a (1-byte) self-relative offset,
  150.          * terminated by a 0; obviously, the chain is sorted by
  151.          * increasing address.  The free list pointers themselves
  152.          * are offsets relative to csbase.
  153.          *
  154.          * Note that these lists overlay the GC relocation table.
  155.          */
  156.     ushort *sfree1;
  157.         /*
  158.          * Free list for blocks of >= 4 bytes.  Each block begins
  159.          * with a 2-byte size and a 2-byte next block pointer,
  160.          * both big-endian.
  161.          */
  162.     ushort sfree;
  163.         /* The remaining members are for the GC. */
  164.     byte *odest;            /* destination for objects */
  165.     byte *smark;            /* mark bits for strings */
  166.     uint smark_size;
  167.     byte *sbase;            /* base for computing smark offsets */
  168.     string_reloc_offset *sreloc;    /* relocation for string blocks */
  169.     byte *sdest;            /* destination for (top of) strings */
  170.     byte *rescan_bot;        /* bottom of rescanning range if */
  171.                     /* the GC mark stack overflows */
  172.     byte *rescan_top;        /* top of range ditto */
  173. };
  174. /* The chunk descriptor is exported only for isave.c. */
  175. extern_st(st_chunk);
  176. #define public_st_chunk()    /* in ialloc.c */\
  177.   gs_public_st_ptrs2(st_chunk, chunk_t, "chunk_t",\
  178.     chunk_enum_ptrs, chunk_reloc_ptrs, cprev, cnext)
  179.  
  180. /*
  181.  * Macros for scanning a chunk linearly, with the following schema:
  182.  *    SCAN_CHUNK_OBJECTS(cp)            << declares pre, size >>
  183.  *        << code for all objects -- size not set yet >>
  184.  *    DO_LARGE
  185.  *        << code for large objects >>
  186.  *    DO_SMALL
  187.  *        << code for small objects >>
  188.  *    END_OBJECTS_SCAN
  189.  * If large and small objects are treated alike, one can use DO_ALL instead
  190.  * of DO_LARGE and DO_SMALL.
  191.  */
  192. #define SCAN_CHUNK_OBJECTS(cp)\
  193.     {    obj_header_t *pre = (obj_header_t *)((cp)->cbase);\
  194.         obj_header_t *end = (obj_header_t *)((cp)->cbot);\
  195.         ulong size;        /* long because of large objects */\
  196.         for ( ; pre < end;\
  197.             pre = (obj_header_t *)((char *)pre + obj_size_round(size))\
  198.             )\
  199.         {
  200. #define DO_LARGE\
  201.             if ( pre->o_large )\
  202.             {    size = pre_obj_large_size(pre);\
  203.                 {
  204. #define DO_SMALL\
  205.                 }\
  206.             } else\
  207.             {    size = pre_obj_small_size(pre);\
  208.                 {
  209. #define DO_ALL\
  210.             {    size = pre_obj_contents_size(pre);\
  211.                 {
  212. #ifdef DEBUG
  213. #  define END_OBJECTS_SCAN\
  214.                 }\
  215.             }\
  216.         }\
  217.         if ( pre != end )\
  218.         {    lprintf2("Chunk parsing error, 0x%lx != 0x%lx\n",\
  219.                  (ulong)pre, (ulong)end);\
  220.             gs_exit(1);\
  221.         }\
  222.     }
  223. #else
  224. #  define END_OBJECTS_SCAN\
  225.                 }\
  226.             }\
  227.         }\
  228.     }
  229. #endif
  230.  
  231. /* Initialize a chunk. */
  232. /* This is exported for save/restore. */
  233. void alloc_init_chunk(P5(chunk_t *, byte *, byte *, bool, chunk_t *));
  234.  
  235. /* Initialize the string freelists in a chunk. */
  236. void alloc_init_free_strings(P1(chunk_t *));
  237.  
  238. /* Find the chunk for a pointer. */
  239. /* Note that ptr_is_within_chunk returns true even if the pointer */
  240. /* is in an inner chunk of the chunk being tested. */
  241. #define ptr_is_within_chunk(ptr, cp)\
  242.   ptr_between((const byte *)(ptr), (cp)->cbase, (cp)->cend)
  243. #define ptr_is_in_inner_chunk(ptr, cp)\
  244.   ((cp)->inner_count != 0 &&\
  245.    ptr_between((const byte *)(ptr), (cp)->cbot, (cp)->ctop))
  246. #define ptr_is_in_chunk(ptr, cp)\
  247.   (ptr_is_within_chunk(ptr, cp) && !ptr_is_in_inner_chunk(ptr, cp))
  248. typedef struct chunk_locator_s {
  249.     const gs_ref_memory_t *memory;    /* for head & tail of chain */
  250.     chunk_t *cp;            /* one-element cache */
  251. } chunk_locator_t;
  252. bool chunk_locate_ptr(P2(const void *, chunk_locator_t *));
  253. #define chunk_locate(ptr, clp)\
  254.   (((clp)->cp != 0 && ptr_is_in_chunk(ptr, (clp)->cp)) ||\
  255.    chunk_locate_ptr(ptr, clp))
  256.  
  257. /* Close up the current chunk. */
  258. /* This is exported for save/restore and for the GC. */
  259. void alloc_close_chunk(P1(gs_ref_memory_t *mem));
  260.  
  261. /* Reopen the current chunk after a GC. */
  262. void alloc_open_chunk(P1(gs_ref_memory_t *mem));
  263.  
  264. /* Insert or remove a chunk in the address-ordered chain. */
  265. /* These are exported for the GC. */
  266. void alloc_link_chunk(P2(chunk_t *, gs_ref_memory_t *));
  267. void alloc_unlink_chunk(P2(chunk_t *, gs_ref_memory_t *));
  268.  
  269. /* Free a chunk.  This is exported for save/restore and for the GC. */
  270. void alloc_free_chunk(P2(chunk_t *, gs_ref_memory_t *));
  271.  
  272. /* Print a chunk debugging message. */
  273. /* Unfortunately, the ANSI C preprocessor doesn't allow us to */
  274. /* define the list of variables being printed as a macro. */
  275. #define dprintf_chunk_format\
  276.   "%s 0x%lx (0x%lx..0x%lx, 0x%lx..0x%lx..0x%lx)\n"
  277. #define dprintf_chunk(msg, cp)\
  278.   dprintf7(dprintf_chunk_format,\
  279.        msg, (ulong)(cp), (ulong)(cp)->cbase, (ulong)(cp)->cbot,\
  280.        (ulong)(cp)->ctop, (ulong)(cp)->climit, (ulong)(cp)->cend)
  281. #define if_debug_chunk(c, msg, cp)\
  282.   if_debug7(c, dprintf_chunk_format,\
  283.         msg, (ulong)(cp), (ulong)(cp)->cbase, (ulong)(cp)->cbot,\
  284.         (ulong)(cp)->ctop, (ulong)(cp)->climit, (ulong)(cp)->cend)
  285.  
  286. /* ================ Allocator state ================ */
  287.  
  288. /* Structures for save/restore (not defined here). */
  289. struct alloc_save_s;
  290. struct alloc_change_s;
  291.  
  292. /* Define the number of freelists.  The index in the freelist array */
  293. /* is the ceiling of the size of the object contents (i.e., not including */
  294. /* the header) divided by obj_align_mod. */
  295. #define max_freelist_size 800        /* big enough for gstate & contents */
  296. #define num_freelists\
  297.   ((max_freelist_size + obj_align_mod - 1) / obj_align_mod + 1)
  298.  
  299. /* Define the memory manager subclass for this allocator. */
  300. struct gs_ref_memory_s {
  301.         /* The following are set at initialization time. */
  302.     gs_memory_common;
  303.     gs_memory_t *parent;        /* for allocating chunks */
  304.     uint chunk_size;
  305.     uint large_size;        /* min size to give large object */
  306.                     /* its own chunk: must be */
  307.                     /* 1 mod obj_align_mod */
  308.     gs_ref_memory_t *global;    /* global VM for this allocator */
  309.                     /* (may point to itself) */
  310.     uint space;            /* a_local, a_global, a_system */
  311.         /* Callers can change the following dynamically */
  312.         /* (through a procedural interface). */
  313.     gs_memory_gc_status_t gc_status;
  314.         /* The following are updated dynamically. */
  315.     ulong limit;            /* signal a VMerror when total */
  316.                     /* allocated exceeds this */
  317.     chunk_t *cfirst;        /* head of chunk list */
  318.     chunk_t *clast;            /* tail of chunk list */
  319.     chunk_t cc;            /* current chunk */
  320.     chunk_t *pcc;            /* where to store cc */
  321.     chunk_locator_t cfreed;        /* chunk where last object freed */
  322.     ulong allocated;        /* total size of all chunks */
  323.                     /* allocated at this save level */
  324.     long inherited;            /* chunks allocated at outer save */
  325.                     /* levels that should be counted */
  326.                     /* towards the GC threshold */
  327.                     /* (may be negative, but allocated + */
  328.                     /* inherited >= 0 always) */
  329.     ulong gc_allocated;        /* value of (allocated + */
  330.                 /* previous_status.allocated) after last GC */
  331.     struct lost_ {            /* space freed and 'lost' */
  332.       ulong objects;
  333.       ulong refs;
  334.       ulong strings;
  335.     } lost;
  336.         /* Garbage collector information */
  337.     gs_gc_root_t *roots;        /* roots for GC */
  338.         /* Sharing / saved state information */
  339.     int num_contexts;        /* # of contexts sharing this VM */
  340.     struct alloc_change_s *changes;
  341.     struct alloc_save_s *saved;
  342.     struct alloc_save_s *reloc_saved;    /* for GC */
  343.     gs_memory_status_t previous_status;    /* total allocated & used */
  344.                     /* in outer save levels */
  345.         /* We put the freelists last to keep the scalar */
  346.         /* offsets small. */
  347.     obj_header_t *freelists[num_freelists];
  348. };
  349. /* The descriptor for gs_ref_memory_t is exported only for */
  350. /* the alloc_save_t subclass; otherwise, it should be private. */
  351. extern_st(st_ref_memory);
  352. #define public_st_ref_memory()    /* in ialloc.c */\
  353.   gs_public_st_composite(st_ref_memory, gs_ref_memory_t,\
  354.     "gs_ref_memory", ref_memory_enum_ptrs, ref_memory_reloc_ptrs)
  355. #define st_ref_memory_max_ptrs 2    /* changes, saved */
  356.  
  357. /* Define the procedures for the standard allocator. */
  358. /* We export this for subclasses. */
  359. extern const gs_memory_procs_t gs_ref_memory_procs;
  360.  
  361. /*
  362.  * Scan the chunks of an allocator:
  363.  *    SCAN_MEM_CHUNKS(mem, cp)
  364.  *        << code to process chunk cp >>
  365.  *    END_CHUNKS_SCAN
  366.  */
  367. #define SCAN_MEM_CHUNKS(mem, cp)\
  368.     {    chunk_t *cp = (mem)->cfirst;\
  369.         for ( ; cp != 0; cp = cp->cnext )\
  370.         {
  371. #define END_CHUNKS_SCAN\
  372.         }\
  373.     }
  374.